class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        sort(nums.begin(), nums.end());
        int i = 0;
        int n = nums.size();
        while (i < n && nums[i] < 0 && k)
        {
            nums[i] = -nums[i];
            ++i;
            --k;
        }

        if (k & 1)
        {
            if (i == n)
            {
                nums[n - 1] = -nums[n - 1];
            }
            else if (i == 0)
            {
                nums[0] = -nums[0];
            }
            else if (nums[i] < nums[i - 1])
            {
                nums[i] = -nums[i];
            }
            else
            {
                nums[i - 1] = -nums[i - 1];
            }
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }
};